A Residual Based Sparse Approximate Inverse Preconditioning Procedure for Large Sparse Linear Systems

摘要

The SPAI algorithm, a sparse approximate inverse preconditioning techniquefor large sparse linear systems, proposed by Grote and Huckle [SIAM J. Sci.Comput., 18 (1997), pp.~838--853.], is based on the F-norm minimization andcomputes a sparse approximate inverse $M$ of a large sparse matrix $A$adaptively. However, SPAI may be costly to seek the most profitable indices ateach loop and $M$ may be ineffective for preconditioning. In this paper, wepropose a residual based sparse approximate inverse preconditioning procedure(RSAI), which, unlike SPAI, is based on only the {\em dominant} rather than allinformation on the current residual and augments sparsity patterns adaptivelyduring the loops. RSAI is less costly to seek indices and is more effective tocapture a good approximate sparsity pattern of $A^{-1}$ than SPAI. To controlthe sparsity of $M$ and reduce computational cost, we develop a practicalRSAI($tol$) algorithm that drops small nonzero entries adaptively during theprocess. Numerical experiments are reported to demonstrate that RSAI($tol$) isat least competitive with SPAI and can be considerably more efficient andeffective than SPAI. They also indicate that RSAI($tol$) is comparable to thePSAI($tol$) algorithm proposed by one of the authors in 2009.